/*
 * =====================================================================================
 *
 *       Filename:  main.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  11/27/2012 09:28:33 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <iterator> 

using namespace std;


static const size_t kInfinity = 10000000;

struct session;

struct query
{
    query(int sid, int time) : sid_(sid), time_(time), id_(0), serp_(0), repeat_cnt_(0) {}

    int sid_;
    int id_;
    int time_;
    int serp_;
    int repeat_cnt_;
    vector<int> urls_;
};

struct metadata
{
    metadata(int sid, int time) : sid_(sid), time_(time), user_(0) {}

    int sid_;
    int time_;
    int user_;
    vector<char> switches_;
};

struct click
{
    click(int sid, int time) : sid_(sid), time_(time_), serp_(0), url_(0) {}

    int sid_;
    int time_;
    int serp_;
    int url_;
};
struct session
{
    session(int id = 0) : id_(id), user_(0), switches_cnt_(0) {}

    bool was_switch() const { return switches_cnt_ > 0; }
    int clicks_cnt() const  { return clicks_.size(); }
    unsigned queries_with_clicks(unsigned min_val, int dist = 0) const
    {
        unsigned res = 0;
        for (size_t i = 0 ; i < queries_.size(); ++i)
        {
            unsigned cnt = 0;
            for (size_t j = 0; j < clicks_.size(); ++j)
                if (queries_[i].serp_ == clicks_[j].serp_)
                    ++cnt;

            if (min_val <= cnt && cnt <= min_val + dist)
                ++res;
        }
        return res;
    }

    void get_queries(vector<int>& res) const
    {
        //set<int> tmp;
        for (size_t i = 0; i < queries_.size(); ++i)
            res.push_back(queries_[i].id_);

        //copy(tmp.begin(), tmp.end(), back_inserter(res));
    }

    void get_urls(vector<int>& res) const
    {
        //set<int> tmp;
        for (size_t i = 0; i < queries_.size(); ++i)
            for (size_t j = 0; j < queries_[i].urls_.size(); ++j)
                res.push_back(queries_[i].urls_[j]);

        //copy(tmp.begin(), tmp.end(), back_inserter(res));
    }

    int id_;
    unsigned switches_cnt_;
    //unsigned clicks_cnt_;
    int user_;
    int day_;
    vector<click> clicks_;
    vector<query> queries_;
    vector<char> switches_;
};




unordered_map<int, session> sessions;
unordered_map<int, vector< int > >  user_session;
size_t pos_cnt = 0, neg_cnt = 0;
typedef unordered_map<int, pair<int, int> > distribution_map;
unordered_map<int, pair<int, int> > prob;
unordered_map<int, pair<int, int> > prob_clicks;
unordered_map<int, pair<int, int> > prob_queries;
unordered_map<int, pair<int, int> > prob_queries0;
unordered_map<int, pair<int, int> > prob_queries1;
unordered_map<int, pair<int, int> > prob_queries2;
unordered_map<int, pair<int, int> > prob_queries3;
unordered_map<int, pair<int, int> > prob_queries4;
unordered_map<int, pair<int, int> > prob_queries5;
unordered_map<int, pair<int, int> > prob_users;

void
compute_stat();

void
read_query(istream& is, session& s, int time)
{
    query q(s.id_, time);
    int url;

    is >> q.serp_ >> q.id_;
    while (is >> url)
        q.urls_.push_back(url);

    s.queries_.push_back(q);
}

void
read_metadata(istream& is, session& s, int time)
{
    char stype;

    s.day_ = time;
    is >> s.user_;
    while (is >> stype)
        s.switches_.push_back(stype);


    user_session[s.user_].push_back(s.id_);
}

void
read_click(istream& is, session& s, int time)
{
    click c(s.id_, time);

    is >> c.serp_ >> c.url_;
    s.clicks_.push_back(c);
}


//SessionID Day M USERID SwitchType
//SessionID TimePassed Q SERPID QueryID ListOfURLs
//SessionID TimePassed C SERPID URLID
//SessionID TimePassed S



int
read_sessions(const char* path, size_t max_sessions = kInfinity)
{
    ifstream fs(path);
    string line;
    int id;
    int time;
    char type;

    while (getline(fs, line))
    {
        istringstream ss(line);
        if (!(ss >> id >> time >> type))
        {
            cerr << "failed to read session file\n";
            return -1;
        }

        //always update id
        if (sessions.find(id) == sessions.end())
        {
            if (sessions.size() > max_sessions)
            {
                break;
                cout << "computing statistic for temporary result\n";
                compute_stat();
                sessions.clear();
            }

            //initialize sessions
            sessions[id].id_ = id;
        }
        
        switch (type)
        {
            case 'M':
                read_metadata(ss, sessions[id], time);
                break;

            case 'Q':
                read_query(ss, sessions[id], time);
                break;
            case 'S':
                ++sessions[id].switches_cnt_;
                break;

            case 'C':
                //++sessions[id].clicks_cnt_;
                read_click(ss, sessions[id], time);
                break;
        }

    }

    return 0;
}


void
add_stat(session const& s, distribution_map& p, int val)
{
    if (s.was_switch())
    {
        ++p[-1].first;
        ++p[val].first;
    }
    else
    {
        ++p[-1].second;
        ++p[val].second;
    }
}

void
compute_stat()
{
    unordered_map<int, session>::iterator sit;

    for (sit = sessions.begin(); sit != sessions.end(); ++sit)
    {
        if (sit->second.was_switch() > 0)
            ++pos_cnt;
        else
            ++neg_cnt;

        //multiply by url probability
        vector<int> urls, queries;
        sit->second.get_urls(urls);
        sit->second.get_queries(queries);
        //cout << sit->first << " urls count = " << urls.size() << "\n";
        for (vector<int>::iterator it = urls.begin(); it != urls.end(); ++it)
            add_stat(sit->second, prob, *it);
        for (vector<int>::iterator it = queries.begin(); it != queries.end(); ++it)
            add_stat(sit->second, prob_queries, *it);


        //add_stat(sit->second, prob_queries, sit->second.get_queries_repeat());

        add_stat(sit->second, prob_queries0, sit->second.queries_with_clicks(0));
        add_stat(sit->second, prob_queries1, sit->second.queries_with_clicks(1));
        add_stat(sit->second, prob_queries2, sit->second.queries_with_clicks(2, kInfinity));
        //add_stat(sit->second, prob_queries3, sit->second.queries_with_clicks(3));
        //add_stat(sit->second, prob_queries4, sit->second.queries_with_clicks(4));
        //add_stat(sit->second, prob_queries5, sit->second.queries_with_clicks(5, kInfinity));
        add_stat(sit->second, prob_users, sit->second.user_);
       
        /*
        if (sit->second.was_switch())
        {
            //queries statistic
            ++prob_queries[-1].first;
            ++prob_queries[sit->second.queries_.size()].first;

            ++prob_queries0[-1].first;
            ++prob_queries0[sit->second.queries_with_clicks(0)].first;

            ++prob_queries1[-1].first;
            ++prob_queries1[sit->second.queries_with_clicks(1)].first;
            
            //clicks statistic
            ++prob_clicks[-1].first;
            ++prob_clicks[sit->second.clicks_cnt()].first;

            ++prob_users[-1].first;
            ++prob_users[sit->second.user_].first;
        }
        else
        {
            //queries statistic
            ++prob_queries[-1].second;
            ++prob_queries[sit->second.queries_.size()].second;

            ++prob_queries0[-1].second;
            ++prob_queries0[sit->second.queries_with_clicks(0)].second;
           
            ++prob_queries1[-1].second;
            ++prob_queries1[sit->second.queries_with_clicks(1)].second;

            //clicks statistic 
            ++prob_clicks[-1].second;
            ++prob_clicks[sit->second.clicks_cnt()].second;

            ++prob_users[-1].second;
            ++prob_users[sit->second.user_].second;
        }*/
    }
}


struct session_prob
{
    session_prob(int id, double prob) : id_(id), prob_(prob) {}
    
    bool operator<(const session_prob& s) const
    {
        return prob_ > s.prob_;
    }

    int id_;
    double prob_;
};


double
update_prob(distribution_map& d, int val)
{
    if (d.find(val) != d.end())
    {

        double pos = static_cast<double>(d[val].first + 1) / (d[-1].first + d.size() - 1);
        double neg = static_cast<double>(d[val].second + 1) / (d[-1].second + d.size() - 1);
        return pos / neg;

        
        //if (val == 26004327)
        //{
        //   cout << "val first " << p[val].first
        //         << " val second " << p[val].second
        //         << " -1 first " << p[-1].first
        //         << " -1 second " << p[-1].second << "\n";
        //}
        //aprior_prob *= tmp;
    }
    return 1.0; //the same probability for unseen value
}



double
compute_query_prob(query& q)
{
    double p = static_cast<double>(prob[-1].first) / (prob[-1].second);

    for (vector<int>::iterator it = q.urls_.begin(); it != q.urls_.end(); ++it)
    {
        p *= update_prob(prob, *it);
    }
}

double
compute_session_prob(session& s)
{
    //vector<query>::iterator qit; 
    //vector<int>::iterator uit;

    //pos_prob = static_cast<double>(pos_cnt) / (pos_cnt + neg_cnt);
    //neg_prob = static_cast<double>(neg_cnt) / (pos_cnt + neg_cnt);

    double p = static_cast<double>(pos_cnt) / neg_cnt;

    //multiply by url probability
    vector<int> urls, queries;
    s.get_urls(urls);
    s.get_queries(queries);

    /*if (s.queries_.size() > 0)
    {
        vector< pair<double, double> > qprobs;
        for (size_t i = 0; i < s.queries_.size(); ++i)
        {
            double qpos, qneg;
            compute_query_prob(s.queries_[i], qpos, qneg);
            qprobs.push_back(make_pair(qpos, qneg));
        }
        pos_prob *= qprobs.back().first;
        neg_prob *= qprobs.back().second;
        for (size_t i = 0; i < qprobs.size() - 1; ++i)
        {
            pos_prob *= qprobs[i].first;
            neg_prob *= qprobs[i].first;
        }
    }*/
    
    for (vector<int>::iterator it = urls.begin(); it != urls.end(); ++it)
    {

        //if (s.id_ == 31228)
        //{
        //    cout << s.id_ << " url " << *it << " " << pos_prob << " " << neg_prob << "\n";
        //}

        p *= update_prob(prob, *it);
    }

    for (vector<int>::iterator it = queries.begin(); it != queries.end(); ++it)
    {
        //if (s.id_ == 31228)
        //{
        //    cout << s.id_ << " query " << *it << " " << pos_prob << " " << neg_prob << "\n";
        //}

        p *= update_prob(prob_queries, *it);
    }
    

    //queries with no clicks
    //p *= update_prob(prob_queries0, s.queries_with_clicks(0));                         
    //update_prob(prob_queries1, s.queries_with_clicks(1), pos_prob, neg_prob);
    //update_prob(prob_queries2, s.queries_with_clicks(2, kInfinity), pos_prob, neg_prob);
    //update_prob(prob_queries3, s.queries_with_clicks(3), pos_prob, neg_prob);
    //update_prob(prob_queries4, s.queries_with_clicks(4), pos_prob, neg_prob);
    //update_prob(prob_queries5, s.queries_with_clicks(5, kInfinity), pos_prob, neg_prob);

    //users probability
    
    p *= update_prob(prob_users, s.user_);
    //if (s.id_ == 31228)
    //{
    //    cout << s.id_ << " user " << s.user_ << " " << pos_prob << " " << neg_prob << "\n";
    //}

    return p;
}

void
gen_result()
{
    vector<session_prob> res;
    unordered_map<int, session>::iterator sit;

    for (sit = sessions.begin(); sit != sessions.end(); ++sit)
    {
        double ratio = compute_session_prob(sit->second);

        res.push_back(session_prob(sit->first, ratio));
    }

    sort(res.begin(), res.end());
    
    ofstream os("result.txt");
    for (size_t i = 0; i < res.size(); ++i)
    {
        os << res[i].id_;
        if (i < res.size() - 1)
            os <<"\n";
    }

}

void
test_probs(size_t max_test)
{
    int cnt = 0;
    unordered_map<int, session>::iterator sit;
    vector<query>::iterator qit; 
    vector<int>::iterator uit;


    fstream fsfp("fp.txt", ios_base::out | ios_base::trunc);
    fstream fsfn("fn.txt", ios_base::out | ios_base::trunc);
    size_t tp = 0, tn = 0, fp = 0, fn = 0;
    for (sit = sessions.begin(); sit != sessions.end(); ++sit)
    {
        if (++cnt > max_test)
            break;

        double ratio = compute_session_prob(sit->second);

        bool was_switch = ratio > 1.0;        
        if (was_switch && sit->second.was_switch())
        {
            ++tp;
        }
        else if (was_switch && !sit->second.was_switch())
        {
            fsfp << sit->first << " " << sit->second.queries_with_clicks(0, 100) << " " << ratio  << "\n";
            ++fp;
        }
        else if (!was_switch && sit->second.was_switch())
        {
            fsfn << sit->first << " " << sit->second.queries_with_clicks(0, 100) << " " << ratio << "\n";
            ++fn;
        }
        else
        {
            ++tn;
        }
    }

    cout << "tp:" << tp << " fp:" << fp << " fn:" << fn << " tn:" << tn <<"\n";
}



void
get_queries_stat(session& s, int& prev_cnt, int& past_cnt)
{
    vector<int> cur;
    vector<int> prev;
    vector<int> past;

    s.get_queries(cur);

    size_t i = 0;
    for (; i < user_session[s.user_].size(); ++i)
    {
        session& o = sessions[user_session[s.user_][i]];
        if (s.id_ == o.id_)
            break;
        o.get_queries(prev);
    }
    for (; i < user_session[s.user_].size(); ++i)
    {
        session& o = sessions[user_session[s.user_][i]];
        o.get_queries(past);
    }

    prev_cnt = 0;
    past_cnt = 0;
    for (size_t i = 0; i < cur.size(); ++i)
    {
        if (find(prev.begin(), prev.end(), cur[i]) != prev.end())
            ++prev_cnt;
        if (find(past.begin(), past.end(), cur[i]) != past.end())
            ++past_cnt;
    }
}

const session*
get_prev_session(session const& s)
{
    size_t i = 0;
    for (; i < user_session[s.user_].size(); ++i)
    {
        session& o = sessions[user_session[s.user_][i]];
        if (s.id_ == o.id_)
            break;
    }
    if (i > 0)
        return &sessions[user_session[s.user_][i - 1]];
    return 0;
}

const session*
get_past_session(session const& s)
{
    size_t i = 0;
    for (; i < user_session[s.user_].size(); ++i)
    {
        session& o = sessions[user_session[s.user_][i]];
        if (s.id_ == o.id_)
            break;
    }
    if (i + 1 < user_session[s.user_].size())
        return &sessions[user_session[s.user_][i + 1]];
    return 0;
}

void
add_session_features(const session* s, ostream& os)
{
    os << (s ? s->queries_with_clicks(0) : 0) << " "
       << (s ? s->queries_with_clicks(1) : 0) << " "
       << (s ? s->queries_with_clicks(2) : 0) << " "
       << (s ? s->queries_with_clicks(3) : 0) << " "
       << (s ? s->queries_with_clicks(4) : 0)<< " "
       << (s ? s->queries_with_clicks(5) : 0)<< " "
       << (s ? s->queries_with_clicks(6) : 0)<< " "
       << (s ? s->queries_with_clicks(7) : 0)<< " "
       << (s ? s->queries_with_clicks(8) : 0)<< " "
       << (s ? s->queries_with_clicks(9, kInfinity) : 0) << " ";
}
void
gen_features()
{
    unordered_map<int, session>::iterator sit;
    vector<query>::iterator qit; 
    vector<int>::iterator uit;

    size_t cnt = 0;
    fstream fout("nn.train", ios_base::out | ios_base::trunc);
    for (sit = sessions.begin(); sit != sessions.end(); ++sit)
    {
        session& s = sit->second;


        add_session_features(get_prev_session(s), fout); 
        add_session_features(&s, fout);
        add_session_features(get_past_session(s), fout);

        fout << "\n" << (s.was_switch() ? 1 : -1) << "\n";
        ++cnt;
    }
    cout << cnt << " sessions were added to neural network train file\n";
}

int
main(int argc, char* argv[])
{
    cout << "reading training data\n";
    read_sessions("./dataset/train");
    cout << sessions.size() << " were read\n";

    //clear user_query map
    //user_query.clear();

    //gen_features();
    //return 0;
    cout << "computing statistic\n";
    compute_stat();
    cout << "testing probabilities\n";
    test_probs(1000000);
    
    sessions.clear();
    cout << "reading test data\n";
    read_sessions("./dataset/test");
    cout << sessions.size() << " were read\n";

    cout << "generating result file\n";
    gen_result();
}


